class Solution {
    int maxSubArray(vector<int>& nums, int k) {
        int ans = 0, f = 0;
        int n = nums.size();
        for(int i = 0; i < n * k; ++i)
        {
            f = max(0, f) + nums[i % n];
            ans = max(f, ans);
        }
        return ans;
    }
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        if(k == 1) return maxSubArray(arr, 1);
        int mod = 1e9 + 7;
        int s = reduce(arr.begin(), arr.end());

        long long ans = maxSubArray(arr, 2);
        ans += 1LL * max(s, 0) * (k - 2);
        return ans % mod;
    }
};
